A pen computer is a computer that uses a stylus as a simulated pen for "writing" on the computer screen. The "ink" is simulated by the CPU, drawing the path of the pen on the display. Existing pen computers produce rough, jagged looking ink that considerably impairs their useability.
Recently, a new class of computers that use a pen or stylus as a primary input mechanism has emerged. This class of pen computers includes Personal Digital Assistants (PDAs) and Tablet computers. In a pen computer, the user writes or makes other marks with the stylus on the display screen, typically a Liquid Crystal Display (LCD). Since, of course, actually applying ink to the screen is not practical, such systems are designed to simulate the effect of ink by producing a line on the display that physically coincides with the path of the stylus across the screen. In addition to providing a visible record of what the user has written, the displayed line is valuable feedback to the user to aid in the process of writing. This simulated ink mark is referred to as "inking".
The intent of pen computers is to provide the user with an input mechanism that has the familiarity of pen and paper. Pen computers today and for the foreseeable future, however, have a limitation that causes stylus input to fall considerably short of this goal: the display resolution is far less than the effective resolution of pen and paper. For example, printers typically require a resolution of about 300 pixels per inch or more to produce an image that approaches the sharpness of pen and paper. By contrast, typical LCD displays have a resolution of less than 100 pixels per inch. The visible result of this low resolution is ink that appears rough and jagged. For example, FIG. 1 shows the jagged appearance of the cursive letter "t" as displayed on a typical LCD having low resolution.
The practical consequences of low resolution are: 1) The readability of the user's writing is greatly reduced; 2) The user must write larger to compensate, and therefore can fit less on the screen, effectively reducing the size of the screen; 3) The jagged ink provides false input to the user's visual-motor feedback loop and results in unnecessary motor corrections that reduce the "neatness" of the written input; and 4) the jagged ink reduces the illusion of using pen and paper, reducing the intended familiarity. The result is that users feel less comfortable with the computer.
There is a technique in the computer graphics field for increasing the effective resolution of a computer display, known as "anti-aliasing". In general, anti-aliasing can be applied when drawing a shape of a particular color (the "foreground" color) on a background of another color (the "background" color). In graphics anti-aliasing, pixels with a color intermediate between the foreground color of the shape being drawn and the background color on which the shape is being drawn are used along the edges of the shape to smooth out the edges and reduce their jagged appearance.
This technique can be accomplished by a variety of methods that have been described in the literature. The following simple method is representative of these prior methods. In the prior methods, each pixel is examined, and it is determined what proportion of a particular pixel is covered by the foreground shape, and what proportion of the pixel is covered by the background. Let us call the proportion covered by the background P, which is a number between 0 and 1; then correspondingly, the proportion of the pixel covered by the foreground color will be 1-P, also a number between 0 and 1.
The final color for the pixel is then calculated as a linear blend of the foreground color and the background color, computed independently for each of the red, green, and blue (r, g, and b) components of the colors (collectively, equation (1)). EQU r.sub.pixel =(1-P)*r.sub.foreground +P*r.sub.background EQU g.sub.pixel =(1-P)*g.sub.foreground +P*g.sub.background (1) EQU b.sub.pixel =(1-P)*b.sub.foreground +P*b.sub.background.
In practice, actually computing P according to the proportion of a pixel covered by foreground and background and applying the formula given above for each pixel is too time-consuming, so various equivalent or approximately equivalent methods have been used. For example, for drawing an anti-aliased line, P for a given pixel can be determined from the distance from the line being drawn to the center of the given pixel. This technique of determining the distance from the center of a set of pixels to a line can be done fairly efficiently.
In addition, better results have been obtained by computing a parameter P for use in the linear blending equations given above according to methods that are more complicated than simple coverage of the pixel by foreground and background.
Generally, such methods can be implemented by computing P as a function of the distance from the pixel to the line being drawn. For instance, some methods compute P according to a complex algorithm, such as a weighted average of foreground/background coverage, typically weighted by distance from the pixel center. This can be considered a generalization of the "pixel coverage" algorithm discussed above: the "pixel coverage" algorithm in effect uses a weighted average of foreground/background with a uniform weight throughout the pixel. More generally, the weighting function can be non-uniform, and its non-zero region can extend beyond the pixel boundary. If the weighting function is circularly symmetric, P is purely a function of distance from the pixel center to the line; even if the weighting function isn't circularly symmetric, such as in the case of the uniform one-pixel-square weighting function used in the "pixel coverage" algorithm, taking P to be a function of the distance from the pixel center to the line is a reasonable approximation. This function is often implemented by table lookup. The particular method used to obtain the parameter P does not materially affect the subsequent use of P in the invention to be presented herein.
While anti-aliasing has been applied in computer graphics systems to improve the appearance of text characters and of geometric objects such as lines, circles, and polygons, anti-aliasing has not been used in a computer system to improve the appearance of inking.
In the application of anti-aliasing to inking, there are certain important practical problems that arise, whose completely correct solution is very difficult or impractical, but for which (in accordance with the present invention) good approximate and practical solutions have been developed.
The first problem arises in the solution to the practical problem of reproducing a curved shape that represents a pen stroke, given the periodically sampled pen positions returned by a typical pen and tablet system, and calculating which pixels are near the edge of that curve-shaped stroke and how far they are from its edge. That is, the problem is how to compute the parameter P to be used in the linear blending formula (1).
The theoretically correct solution requires constructing a mathematical description of a curved shape describing the boundaries of a narrow strip following the supposed curve path taken by the stylus, as reconstructed from the periodically sampled stylus positions as returned by the tablet hardware. This solution, however, is too time-consuming for a practical system.
The solution adopted in known non-anti-aliased systems is to treat the pen path as a series of short line segments whose endpoints are the successive sample, or some subset of those samples, returned by the tablet hardware. A similar approach can be adopted in the anti-aliased case, but unlike the non-anti-aliased case, the inventors have determined that special care must be taken as to the treatment of the ends of the line segments in order to avoid apparent gaps between the segments.
The second problem has to do with the practical problem of combining each new line segment as it is produced with the images and graphics already on the screen and with the previous line segments that were drawn. A completely accurate method of anti-aliasing needs to consider for each pixel the geometric relationship of that pixel with each of the objects to be drawn (such as the proportion of that pixel covered by each object) before assigning the pixel a color. In a practical system, objects are drawn on a screen one at a time. For example, the screen may be composed by first drawing a number of windows and other graphical user interface objects. Then, as the user moves the stylus, a number of line segments representing the motion of the stylus will be drawn on the display, one at a time in succession. A practical method is needed for combining the successive anti-aliased line segments with the graphical objects and other anti-aliased line segments that are already on display.
The third problem that arises concerns inking on a color display. The mathematically correct solution for anti-aliased lines involving color is as given above by the linear blending equation (1). However, in a computer system based on a color table, this solution would not be possible to implement because too many different colors would be required to accommodate each of the possible combinations of line color and background color. A practical approximate solution is required.
The foregoing problems are addressed by the present invention.